package com.leetcode.algorithm.y18.m06;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * leetcode-cn.com
 * (done)443. 压缩字符串
 * (done)459. 重复的子字符串 
 * (done)520. 检测大写字母
 * (done)521. 最长特殊序列 Ⅰ 
 * (done)541. 反转字符串 II
 * (done)557. 反转字符串中的单词 III
 * (done)551. 学生出勤纪录 I
 * (done)657. 判断路线成圈
 * (done)696. 计数二进制子串
 * (done)819. 最常见的单词
 * (done)824. 山羊拉丁文 
 * @author: dengjie213@126.com
 * @time: 2018年6月10日 下午12:33:27
 */
public class MySolution0610 {
	/**
	 * 443. 压缩字符串
	 * 给定一组字符，使用原地算法将其压缩。
	 * 压缩后的长度必须始终小于或等于原数组长度。
	 * 数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。
	 * 在完成原地修改输入数组后，返回数组的新长度。
	 * 
	 * 进阶：
	 * 你能否仅使用O(1) 空间解决问题？
	 * 
	 * 示例 1：
	 * 输入：
	 * ["a","a","b","b","c","c","c"]
	 * 输出：
	 * 返回6，输入数组的前6个字符应该是：["a","2","b","2","c","3"]
	 * 说明：
	 * "aa"被"a2"替代。"bb"被"b2"替代。"ccc"被"c3"替代。
	 * 
	 * 示例 2：
	 * 输入：
	 * ["a"]
	 * 输出：
	 * 返回1，输入数组的前1个字符应该是：["a"]
	 * 说明：
	 * 没有任何字符串被替代。
	 * 
	 * 示例 3：
	 * 输入：
	 * ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
	 * 输出：
	 * 返回4，输入数组的前4个字符应该是：["a","b","1","2"]。
	 * 说明：
	 * 由于字符"a"不重复，所以不会被压缩。"bbbbbbbbbbbb"被“b12”替代。
	 * 注意每个数字在数组中都有它自己的位置。
	 * 
	 * 注意：
	 * 所有字符都有一个ASCII值在[35, 126]区间内。
	 * 1 <= len(chars) <= 1000。
	 * @param chars
	 * @return
	 */
	public int compress(char[] chars) {
		int i = 0;
		int len = chars.length;
		while (i < len) {
			char ch = chars[i];
			int cnt = 1;
			while ((i + cnt) < len && ch == chars[i + cnt]) {
				cnt++;
			}
			// 索引为[i,i+cnt-1]的元素相等
			if (cnt == 1) {
				i++;
			} else {
				if (cnt == 2) {
					chars[i + 1] = '2';
					i += 2;
					continue;
				}
				char[] cntArr = Integer.toString(cnt).toCharArray();
				int cntLen = cntArr.length;
				for (int j = 1; j <= cntLen; j++) {
					chars[i + j] = cntArr[j - 1];
				}
				int shift = cnt - cntLen - 1;
				for (int j = i + cnt; j < len; j++) {
					chars[j - shift] = chars[j];
				}
				len = len - shift;
				i = i + cntLen + 1;
			}
		}
		return len;
	}

	/**
	 * 459. 重复的子字符串 
	 * 给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
	 * 
	 * 示例 1:
	 * 输入: "abab"
	 * 输出: True
	 * 解释: 可由子字符串 "ab" 重复两次构成。
	 * 
	 * 示例 2:
	 * 输入: "aba"
	 * 输出: False
	 * 
	 * 示例 3:
	 * 输入: "abcabcabcabc"
	 * 输出: True
	 * 
	 * 解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。) 
	 * @param s
	 * @return
	 */
	public boolean repeatedSubstringPattern(String s) {
		int len = s.length();
		if (len == 1) {
			return false;
		}
		char ch0 = s.charAt(0); // 首字母
		for (int i = 1; i <= (len + 1) / 2; i++) {
			char ch = s.charAt(i);
			if (ch == ch0 && len % i == 0) {
				int beginIdx = i;
				while (beginIdx < len && s.substring(beginIdx).indexOf(s.substring(0, i)) == 0) {
					beginIdx += i;
				}
				if (beginIdx == len) {
					return true;
				}
			}
		}
		return false;
	}

	/**
	 * 520. 检测大写字母
	 * 给定一个单词，你需要判断单词的大写使用是否正确。
	 * 我们定义，在以下情况时，单词的大写用法是正确的：
	 * 	全部字母都是大写，比如"USA"。
	 * 	单词中所有字母都不是大写，比如"leetcode"。
	 * 	如果单词不只含有一个字母，只有首字母大写， 比如 "Google"。
	 * 否则，我们定义这个单词没有正确使用大写字母。
	 * 
	 * 示例 1:
	 * 输入: "USA"
	 * 输出: True
	 * 
	 * 示例 2:
	 * 输入: "FlaG"
	 * 输出: False
	 * 注意: 输入是由大写和小写拉丁字母组成的非空单词。
	 * @param word
	 * @return
	 */
	public boolean detectCapitalUse(String word) {
		int len = word.length();
		if (len == 1) {
			return true;
		}
		char ch0 = word.charAt(0); // 首字母
		if (ch0 >= 'a' && ch0 <= 'z') { // 首字母为小写，则所有字母为小写
			for (int i = 1; i < len; i++) {
				char ch = word.charAt(i);
				if (!(ch >= 'a' && ch <= 'z')) {
					return false;
				}
			}
		} else { // 首字母为大写，则进一步判断第二个字符大小写
			if (len == 2) {
				return true;
			}
			char ch1 = word.charAt(1); // 第二个字符
			if (ch1 >= 'a' && ch1 <= 'z') {// 第二个字符小写，则后续所有字母为小写
				for (int i = 2; i < len; i++) {
					char ch = word.charAt(i);
					if (!(ch >= 'a' && ch <= 'z')) {
						return false;
					}
				}
			} else {// 第二个字符大写，则后续所有字母为大写
				for (int i = 2; i < len; i++) {
					char ch = word.charAt(i);
					if (!(ch >= 'A' && ch <= 'Z')) {
						return false;
					}
				}
			}
		}
		return true;
	}


	/**
	 * 521. 最长特殊序列 Ⅰ 
	 * 给定两个字符串，你需要从这两个字符串中找出最长的特殊序列。最长特殊序列定义如下：该序列为某字符串独有的最长子序列（即不能是其他字符串的子序列）。
	 * 
	 * 子序列可以通过删去字符串中的某些字符实现，但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列，任何字符串为其自身的子序列。
	 * 
	 * 输入为两个字符串，输出最长特殊序列的长度。如果不存在，则返回 -1。
	 * 
	 * 示例 :
	 * 
	 * 输入: "aba", "cdc"
	 * 输出: 3
	 * 解析: 最长特殊序列可为 "aba" (或 "cdc")
	 * 说明:
	 * 
	 * 两个字符串长度均小于100。
	 * 字符串中的字符仅含有 'a'~'z'。 
	 * @param a
	 * @param b
	 * @return
	 */
	public int findLUSlength(String a, String b) {
		if (a.equals(b)) {
			return -1;
		}
		return Math.max(a.length(), b.length());
	}

	/**
	 * 541. 反转字符串 II
	 * 给定一个字符串和一个整数 k，你需要对从字符串开头算起的每个 2k 个字符的前k个字符进行反转。如果剩余少于 k 个字符，则将剩余的所有全部反转。如果有小于 2k 但大于或等于 k 个字符，则反转前 k 个字符，并将剩余的字符保持原样。
	 * 
	 * 示例:
	 * 
	 * 输入: s = "abcdefg", k = 2
	 * 输出: "bacdfeg"
	 * 要求:
	 * 
	 * 该字符串只包含小写的英文字母。
	 * 给定字符串的长度和 k 在[1, 10000]范围内。
	 * @param s
	 * @param k
	 * @return
	 */
	public String reverseStr(String s, int k) {
		if (k == 1) {
			return s;
		}
		int beginIdx = 0;
		int endIdx = 0;
		StringBuffer ret = new StringBuffer();
		while (beginIdx < s.length()) {
			endIdx = Math.min(beginIdx + k, s.length());
			ret.append(new StringBuffer(s.substring(beginIdx, endIdx)).reverse().toString());
			beginIdx = endIdx;
			if (beginIdx < s.length()) {
				endIdx = Math.min(beginIdx + k, s.length());
				ret.append(s.substring(beginIdx, endIdx));
				beginIdx = endIdx;
			}
		}
		return ret.toString();
	}

	/**
	 * 557. 反转字符串中的单词 III
	 * 给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
	 * 
	 * 示例 1:
	 * 
	 * 输入: "Let's take LeetCode contest"
	 * 输出: "s'teL ekat edoCteeL tsetnoc" 
	 * 注意：在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。
	 * @param s
	 * @return
	 */
	public String reverseWords(String s) {
		StringBuffer ret = new StringBuffer();
		String[] words = s.split(" ");
		for (int i = 0; i < words.length; i++) {
			if (i != 0) {
				ret.append(" ");
			}
			ret.append(new StringBuffer(words[i]).reverse());
		}
		return ret.toString();
	}

	/**
	 * 551. 学生出勤纪录 I
	 * 给定一个字符串来代表一个学生的出勤纪录，这个纪录仅包含以下三个字符：
	 * 
	 * 'A' : Absent，缺勤
	 * 'L' : Late，迟到
	 * 'P' : Present，到场
	 * 如果一个学生的出勤纪录中不超过一个'A'(缺勤)并且不超过两个连续的'L'(迟到),那么这个学生会被奖赏。
	 * 你需要根据这个学生的出勤纪录判断他是否会被奖赏。
	 * 
	 * 示例 1:
	 * 输入: "PPALLP"
	 * 输出: True
	 * 
	 * 示例 2:
	 * 输入: "PPALLL"
	 * 输出: False
	 * @param s
	 * @return
	 */
	public boolean checkRecord(String s) {
		return s.indexOf("LLL") < 0 && s.indexOf('A') == s.lastIndexOf('A');
	}
	
	/**
	 * 657. 判断路线成圈
	 * 初始位置 (0, 0) 处有一个机器人。给出它的一系列动作，判断这个机器人的移动路线是否形成一个圆圈，换言之就是判断它是否会移回到原来的位置。
	 * 移动顺序由一个字符串表示。每一个动作都是由一个字符来表示的。机器人有效的动作有 R（右），L（左），U（上）和 D（下）。输出应为 true 或 false，表示机器人移动路线是否成圈。
	 * 
	 * 示例 1:
	 * 输入: "UD"
	 * 输出: true
	 * 
	 * 示例 2:
	 * 输入: "LL"
	 * 输出: false
	 * @param moves
	 * @return
	 */
	public boolean judgeCircle(String moves) {
		int countL = 0;
		int countU = 0;
		for (int i = 0; i < moves.length(); i++) {
			char ch = moves.charAt(i);
			if (ch == 'L') {
				countL++;
			} else if (ch == 'R') {
				countL--;
			} else if (ch == 'U') {
				countU++;
			} else {
				countU--;
			}

		}
		return countL == 0 && countU == 0;
	}
    
    /**
     * 696. 计数二进制子串
	 * 给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。
	 * 重复出现的子串要计算它们出现的次数。
	 * 
	 * 示例 1 :
	 * 输入: "00110011"
	 * 输出: 6
	 * 解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。
	 * 请注意，一些重复出现的子串要计算它们出现的次数。
	 * 另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。
	 * 
	 * 示例 2 :
	 * 输入: "10101"
	 * 输出: 4
	 * 解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。
	 * 注意：
	 * 
	 * s.length 在1到50,000之间。
	 * s 只包含“0”或“1”字符。
     * @param s
     * @return
     */
	public int countBinarySubstrings(String s) {
		int len = s.length();
		int cnt = 0;
		int idx = s.indexOf("01");
		while (idx >= 0) {
			cnt++;
			int j = 1;
			while (idx - j >= 0 && idx + 1 + j < len && s.charAt(idx - j) == '0' && s.charAt(idx + 1 + j) == '1') {
				cnt++;
				j++;
			}
			idx = s.indexOf("01", idx + 1);
		}
		idx = s.indexOf("10");
		while (idx >= 0) {
			cnt++;
			int j = 1;
			while (idx - j >= 0 && idx + 1 + j < len && s.charAt(idx - j) == '1' && s.charAt(idx + 1 + j) == '0') {
				cnt++;
				j++;
			}
			idx = s.indexOf("10", idx + 1);
		}
		return cnt;
	}
    
    /**
     * 819. 最常见的单词
	 * 给定一个段落 (paragraph) 和一个禁用单词列表 (banned)。返回出现次数最多，同时不在禁用列表中的单词。题目保证至少有一个词不在禁用列表中，而且答案唯一。
	 * 禁用列表中的单词用小写字母表示，不含标点符号。段落中的单词不区分大小写。答案都是小写字母。
	 * 
	 * 示例:
	 * 输入: 
	 * paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
	 * banned = ["hit"]
	 * 输出: "ball"
	 * 解释: 
	 * "hit" 出现了3次，但它是一个禁用的单词。
	 * "ball" 出现了2次 (同时没有其他单词出现2次)，所以它是段落里出现次数最多的，且不在禁用列表中的单词。 
	 * 注意，所有这些单词在段落里不区分大小写，标点符号需要忽略（即使是紧挨着单词也忽略， 比如 "ball,"）， 
	 * "hit"不是最终的答案，虽然它出现次数更多，但它在禁用单词列表中。
	 * 
	 * 说明:
	 * 1 <= 段落长度 <= 1000.
	 * 1 <= 禁用单词个数 <= 100.
	 * 1 <= 禁用单词长度 <= 10.
	 * 答案是唯一的, 且都是小写字母 (即使在 paragraph 里是大写的，即使是一些特定的名词，答案都是小写的。)
	 * paragraph 只包含字母、空格和下列标点符号!?',;.
	 * paragraph 里单词之间都由空格隔开。
	 * 不存在没有连字符或者带有连字符的单词。
	 * 单词里只包含字母，不会出现省略号或者其他标点符号。
     * @param paragraph
     * @param banned
     * @return
     */
	public String mostCommonWord(String paragraph, String[] banned) {
		Set<String> bannedSet = new HashSet<String>();
		for (String str : banned) {
			bannedSet.add(str);
		}
		String[] words = paragraph.replaceAll("[!?',;.]", "").toLowerCase().split(" ");

		int maxCnt = 0; // 单词出现次数的最大值
		String commonWord = ""; // 最常见的单词
		Map<String, Integer> cntMap = new HashMap<String, Integer>();// K为单词，V为单词出现次数
		for (int i = 0; i < words.length; i++) {
			String str = words[i];
			if (!bannedSet.contains(str)) {
				Integer cnt = cntMap.get(str);
				if (cnt == null) {
					cntMap.put(str, 1);
					if ("".equals(commonWord)) {
						maxCnt = 1;
						commonWord = str;
					}
				} else {
					cnt++;
					cntMap.put(str, cnt);
					if (cnt > maxCnt) {
						maxCnt = cnt;
						commonWord = str;
					}
				}
			}
		}
		return commonWord;
	}
    
    /**
     * 824. 山羊拉丁文
	 * 给定一个由空格分割单词的句子 S。每个单词只包含大写或小写字母。
	 * 我们要将句子转换为 “Goat Latin”（一种类似于 猪拉丁文 - Pig Latin 的虚构语言）。
	 * 
	 * 山羊拉丁文的规则如下：
	 * 如果单词以元音开头（a, e, i, o, u），在单词后添加"ma"。
	 * 例如，单词"apple"变为"applema"。
	 * 如果单词以辅音字母开头（即非元音字母），移除第一个字符并将它放到末尾，之后再添加"ma"。
	 * 例如，单词"goat"变为"oatgma"。
	 * 根据单词在句子中的索引，在单词最后添加与索引相同数量的字母'a'，索引从1开始。
	 * 例如，在第一个单词后添加"a"，在第二个单词后添加"aa"，以此类推。
	 * 返回将 S 转换为山羊拉丁文后的句子。
	 * 
	 * 示例 1:
	 * 输入: "I speak Goat Latin"
	 * 输出: "Imaa peaksmaaa oatGmaaaa atinLmaaaaa"
	 * 
	 * 示例 2:
	 * 输入: "The quick brown fox jumped over the lazy dog"
	 * 输出: "heTmaa uickqmaaa rownbmaaaa oxfmaaaaa umpedjmaaaaaa overmaaaaaaa hetmaaaaaaaa azylmaaaaaaaaa ogdmaaaaaaaaaa"
	 * 
	 * 说明:
	 * S 中仅包含大小写字母和空格。单词间有且仅有一个空格。
	 * 1 <= S.length <= 150。
     * @param S
     * @return
     */
	public String toGoatLatin(String S) {
		StringBuffer ret = new StringBuffer();
		String[] words = S.split(" ");
		for (int i = 0; i < words.length; i++) {
			if (i != 0) {
				ret.append(" ");
			}
			String str = words[i];
			char ch = str.charAt(0);
			if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' || ch == 'A' || ch == 'E' || ch == 'I'
					|| ch == 'O' || ch == 'U') {
				ret.append(str);
			} else {
				ret.append(str.substring(1)).append(ch);
			}
			ret.append("ma");
			for (int j = 0; j <= i; j++) {
				ret.append("a");
			}
		}
		return ret.toString();
	}
}
